1. Field of the Invention
This invention relates broadly to deductive spreadsheets. More particularly, this invention relates to a user programmable deductive spreadsheet that supports recursive definitions.
2. State of the Art
Deductive spreadsheets are the subject of DARPA Topic Number SB043-040. Generally, a deductive spreadsheet is a computer program which allows logic programming via a familiar spreadsheet user interface. Traditional spreadsheet programs allow an end user to “program” a spreadsheet to perform elaborate and complex mathematical computations using a very high level intuitive interface which is relatively easy to learn compared to a lower level computer programming language. The first computer spreadsheet program was introduced in 1979 and since then spreadsheet programs have become an indispensable and familiar part of many businesses.
Logic programming, also known as mechanical deduction and machine-assisted reasoning is the key component of many intelligent computing applications. Intelligent computing applications include applications such as robotics, expert systems, financial planning, decision support and logistics. Typically, in these types of applications, knowledge of the application domain is encoded within a knowledge base and an inference engine makes decisions and/or answers questions based on the contents of the knowledge base. There are several specialized logic programming languages because logic programming with a general purpose programming language is extremely complex. One of the most widely used logic programming languages is Prolog.
A Prolog program consists of a database of facts and rules denoting logical relationships that relate to the given application. Specifically facts and rules are expressed using the syntax “head:-body.”, where head is a literal and body is a conjunct of literals. The head is true whenever the body is true. A head with an empty body is a fact and is unconditionally true. Rather than running a Prolog program to obtain a solution, the user asks a question. When asked a question, the Prolog run time system searches through the database of facts and rules to determine (by logical deduction) the answer.
Prolog programs are declarative. Rules are used to express relationships between entities, and these rules are used to find solutions to queries using a theorem-proving approach, namely resolution. Because logic programming languages are inherently “high-level”, i.e. they focus on the computation's logic and not on its mechanics, programmers can focus on expressing complex ideas without worrying about low-level details of memory management, stack pointers, etc. Nevertheless, one still has to be well versed in the language in order to program the problem. Indeed programming problems requiring non-trivial and elaborate reasoning are beyond the capabilities of end users who are not trained as programmers.
Deductive spreadsheets attempt to meet the need of end users who desire to create relatively complex logic programs to meet their specific needs. It is well recognized that end user programmers outnumber professional programmers and this trend is projected to grow. A recent study released by Carnegie Mellon University School of Computer Science estimates that in 2012, there will be 90 million end-user programmers in American workplaces. Of these, over 55 million will use spreadsheets or databases According to DARPA Topic SB043-040, it is expected that “the spreadsheet approach should make authoring, maintaining and using a rule-base easier. We do expect a ‘deductive spreadsheet’ may require additional training over a trivial spreadsheet. We would expect the users to be military staff officers, engineers and scientists (such as biologists) constructing and using theories/models of the battlefield situation, courses of action and scientific phenomena.”
Gopal Gupta and S. F. Akhter, “Knowledgesheet: A graphical spreadsheet interface for interactively developing a class of constraint programs”, Proc. of Practical Aspects of Declarative Languages, LNCS Vol. 1753, 2000 and M. Kasoff, L. M. Zen, A. Garg and M. Genesereth, “PrediCalc: A logical spreadsheet management system”, 31st Intl. Conf. on Very Large Databases, 2005 both disclose extensions to traditional spreadsheets which allow the user to specify constraints on the values of cells. Cells are still required to contain single values, but those values may be partially (or totally) determined by constraints. Constraints may be arithmetic, Boolean, etc.
In Knowledgesheet, finite-domain constraints are associated with cells and specify combinatorial problems. Upon user request, the system converts these constraints into a CLP(FD) program, executes it, and returns the solution as cell values. Those skilled in the art will appreciate that CLP(FD) means constraint logic programming (finite domain).
In PrediCalc, the constraint-solving engine is more integrated into spreadsheet interaction, and issues addressed include how to handle over-specified (or inconsistent) values and under-specified values. However, neither Knowledgesheet nor PrediCalc supports full deduction. In particular they do not support recursive definitions.